package string;

/**
 * Longest Common Subsequence
 * 
 * Timing Complexity: O(n.m)
 * */
public class LCS {

	/**
	 * This method returns longest common subsequence of two strings
	 * 
	 * @param  first string
	 * @param  second string
	 * @return  longest common subsequence
	 * */
	public static String findLCS(String str1, String str2){

		int len1 = str1.length();
		int len2 = str2.length();

		int[][] matrix = new int[len1+1][len2+1];

		// fill the matrix
		for(int i = 0; i < len1; i++){
			for(int j = 0; j < len2; j++){

				if(str1.charAt(i) == str2.charAt(j)){
					matrix[i+1][j+1] = matrix[i][j] + 1;
				}else {
					int val1 = 0;
					int val2 = 0;

					//if(i > 0){
						val1 = matrix[i][j+1];
					//} 
					
					//if(j > 0){
						val2 = matrix[i+1][j];
					//} 
					
					if(val1 > val2){
						matrix[i+1][j+1] = val1;
					}else{
						matrix[i+1][j+1] = val2;
					}
				}
				
				//printMatrix(matrix);
				//System.out.println();
			}
		}

		//printMatrix(matrix);
		
		StringBuffer lcs = new StringBuffer();

		int i = len1; 
		int j = len2;
		
		// extract lcs by traversing through matrix
		while(i > 0 && j > 0){
			
			if(matrix[i-1][j] == matrix[i][j]){
				i--;
			}else if(matrix[i][j-1] == matrix[i][j]){
				j--;
			}else{
				lcs.append(str1.charAt(i-1));
				i--;
				j--;
			}
		}	
		
		return lcs.reverse().toString();
	}

	
	public static void main(String[] args){
		System.out.println(findLCS("gac", "agcat")); // ans: ga
		System.out.println(findLCS("XMJYAUZ", "MZJAWXU")); // ans: mjau
		
	}
	
	/**
	 * Helper method to print matrix
	 * */
	private static void printMatrix(int[][] matrix){
		
		System.out.println("matrix:");
		int rowCount = matrix.length;
		int columnCount = matrix[0].length;
			
		for(int i = 0; i < rowCount; i++){
			for(int j = 0; j < columnCount; j++){
				System.out.print(matrix[i][j]);	
			}
			System.out.println();
		}
		System.out.println("-------------");
	}
}
